package sort;

import java.util.Arrays;

public class Sort {
    //实现插入排序
    //把整个数组分为两部分，左边为有序区，右边为无序区
    //从右边的第一个元素开始，与有序区的元素比较，如果比它小，则交换位置，直到找到合适的位置
    //然后把这个元素插入到有序区的正确位置
    //循环n-1次
    public static void insertSort(int[] arr) {
        //bound 变量表示边界
        //【0,bound)是有序区间
        //【bound,arr.length)是无序区间
        //此处是无序区间
        for (int bound = 1; bound < arr.length; bound++) {
            //取无序区间第一个元素
            int value = arr[bound];
            //从有序区间的最后一个元素开始比较
            int cur = bound - 1;//取有序区间最后一个元素的下标
            //从右边的第一个元素开始比较，直到找到合适的位置
            for (; cur >= 0; cur--) {
                //如果当前元素大于要插入的元素，则将当前元素向后移动一位
                if (arr[cur] > value) {
                    arr[cur + 1] = arr[cur];
                } else {
                    break;
                }
            }
            arr[cur + 1] = value;
        }
    }

    //希尔排序
    //分组，对每组进行插入排序
    //分组的大小为gap，gap为数组长度的一半
    //此处使用希尔序列 gap=size/2，size/4，size/8
    public static void shellSort(int[] arr) {
        int gap = arr.length / 2;
        while (gap >= 1) {
            insertSortgap(arr, gap);
            gap /= 2;
        }
    }

    public static void insertSortgap(int[] arr, int gap) {
        for (int bound = gap; bound < arr.length; bound++) {
            //value表示gap表示的第一个元素
            int value = arr[bound];
            //cue取出value所在组的前一个元素的下标
            int cur = bound - gap;
            for (; cur >= 0; cur -= gap) {
                if (arr[cur] > value) {
                    //将当前元素向后移动gap个位置
                    arr[cur + gap] = arr[cur];
                } else {
                    break;
                }
            }
            arr[cur + gap] = value;
        }
    }

    //选择排序核心思想 每次从待排序区间中找打最小值，放到已排序区间的末尾
    //这个找最小值的过程称为打擂台，以待排序区间的第一个元素为起点，然后与其他元素挨个比较，取最小值
    private static void selectSort(int[] arr) {
        //[0,bound)是已排序区间
        //[bound,arr.length)是待排序区间
        //此处是待排序区间
        //当bound=arr.length-1时，表示已排序区间的右边界
        for (int bound = 0; bound < arr.length - 1; bound++) {
            int min = bound;
            for (int i = bound + 1; i < arr.length; i++) {
                if (arr[i] < arr[min]) {
                    int temp = arr[i];
                    arr[i] = arr[min];
                    arr[min] = temp;
                }
            }
            System.out.println(bound + " " + Arrays.toString(arr));
        }
    }

    //堆排序
    //建大堆（升序）
    //把堆顶元素和堆的最后一个元素交换位置，然后向下调整堆
    public static void heapSort(int[] arr) {
        //1建堆
        creatHeap(arr);
        //2依次把堆顶元素和待排序区间的最后一个元素交换
        //此处我们设定【0  bound）为待排区间，也就是说堆顶元素为arr[0]
        int bound = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {
            //交换堆顶元素和堆的最后一个元素
            int temp = arr[0];
            arr[0] = arr[bound];
            arr[bound] = temp;
            //向下调整堆
            shiftDown(arr,  bound, 0);
            bound--;
        }
    }
    //建堆
    public static void creatHeap(int[] arr) {
        //从最后一个非叶子节点
        for(int i=(arr.length-1-1)/2;i>=0;i--){
            shiftDown( arr,arr.length,i);
        }

    }
    //向下调整堆
    //这个向下调整就是建大堆的过程
    public static void shiftDown(int[] arr, int length, int index) {
        int parent = index;
        int child = 2 * parent + 1;
        while (child < length) {
            if (child + 1 < length && arr[child] < arr[child + 1]) {
                child++;
            }
            if (arr[parent] < arr[child]){
                int temp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = temp;
            }else{
                break;
            }
            //更新
            parent=child;
            child=parent*2+1;
        }
    }

    //冒泡排序
    //比较两个相邻元素，如果前者大于后者，则交换位置
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    //快速排序
    //选取一个元素作为基准，将比基准小的元素放到左边，大的元素放到右边
    //然后分别对左右两边的子数组进行快速排序
    public static void quickSort(int[] arr) {
        quickSort(arr,0,arr.length-1);
    }
    //快速排序，辅助递归的方法
    //此处约定[left,right]闭区间为处理待处理区间
    private static void quickSort(int[] arr, int left, int right) {
     if(left>=right){
         return ;
     }
     int index=partition(arr,left,right);
     //递归左版区间
     quickSort(arr,left,index-1);
     //递归右版区间
     quickSort(arr,index+1,right);
    }

    //这里需要注意选择基准数的位置，以及循环反向
    //如果选取左侧的元素作为基准数，那么先从右往左找小于基准数的元素，再从左往右找大于基准数的元素
    //如果选取右侧的元素作为基准数，那么先从左往右找大于基准数的元素，再从右往左找小于基准数的元素

    private static int partition(int[] arr, int left, int right) {
        //选取最右侧的元素作为基准元素
        int value=arr[right];
        //设定两个下标，分别从左往右和从右往左
        int i=left;
        int j=right;
        while(i<j){
            //从左往右找大于基准元素的元素
            while(i<j&&arr[i]<=value){
                i++;
            }
            //从右往左找小于基准元素的元素
            while(i<j&&arr[j]>=value){
                j--;
            }
            //交换两个元素
            if(i<j){
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
            }
        //把重合的元素与基准值交换
        //将基准元素放到中间
        int temp=arr[i];
        arr[i]=arr[right];
        arr[right]=temp;
        return i;

        }
        //归并排序
     private static void mergeSort(int[] arr) {
         mergeSort(arr,0,arr.length-1);
    }
    //归并排序，辅助递归的方法
    //此处约定[left,right]闭区间为处理待处理区间
    private static void mergeSort(int[] arr, int left, int right) {
        //1:如果子区间中没有元素，或者只有一个元素，则不需要递归
        if(left>=right){
            return ;
        }
        //2:计算子区间的中间位置
        int mid=(left+right)/2;
        //3:递归左半边
        mergeSort(arr,left,mid);
        //4:递归右半边
        mergeSort(arr,mid+1,right);
        //5:合并两个有序子区间
        merge(arr,left,mid,right);
    }
    //合并两个有序子区间
    private static void merge(int[] arr, int left, int mid, int right) {
        //1:创建辅助数组
        int[] result = new int[right - left + 1];
        int resultSize=0;
        //2谁当两个下标指向每个区间的开通位置
        int cur = left;
        int cur2=mid+1;
        while(cur<=mid&&cur2<=right){
            if(arr[cur]<arr[cur2]){
                result[resultSize++]=arr[cur++];
            }else{
                result[resultSize++]=arr[cur2++];
            }
        }
        //3:将剩余元素添加到辅助数组
        while(cur<=mid){
            result[resultSize++]=arr[cur++];
        }
        while(cur2<=right){
            result[resultSize++]=arr[cur2++];
        }
        //4:将辅助数组中的元素复制回原数组
        for(int i=0;i<resultSize;i++) {
            arr[left + i] = result[i];
        }
    }


    public static void main(String[] args) {
        //验证插入排序
        int[] arr={9,5,2,7,3,6,8};
//        insertSort(arr);
       // shellSort(arr);
        //selectSort(arr);
        //heapSort(arr);
       // bubbleSort(arr);
        quickSort(arr);
        System.out.println(Arrays.toString(arr));

    }
}

